package advance.x000.acw_96;

public class Main {

    // n个盘子4座塔
    public static void main(String[] args) {
        int N = 12;
        int[] hanoi = new int[N+1];
        hanoi[1] = 1;
        int[] d = new int[N+1];
        d[1] = 1;
        for (int i = 2; i <= N; i++) {
            d[i] = 2 * d[i - 1] + 1;
            hanoi[i]=Integer.MAX_VALUE;
        }

        for (int i = 2; i <= N; i++) {
            for (int k = 1; k < i; k++) {
                hanoi[i] = Math.min(2 * hanoi[k] + d[i - k], hanoi[i]);
            }
        }
        for (int i = 1; i <= N; i++) {
            System.out.println(hanoi[i]);
        }
    }

}
